package _1_单调栈

/*
*
https://leetcode.cn/problems/largest-rectangle-in-histogram/

84. 柱状图中最大的矩形       直方图内最大矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：
输入： heights = [2,4]
输出： 4

	  *
	* *
	* *
	* *   *

*	* * * *
* * * * * *
2 1 5 6 2 3

题意: 这些柱子组成的最大矩形面积为: 5和6形成的矩形, 面积为2*5 = 10

思路:
遍历数组, 找到当前元素, 左边比小于自己的柱子, 右边小于自己的柱子
例如元素1, 左边和右边都找不到比自己小的, 说明当前元素构成的矩形宽度可以贯穿整个柱状图
所以, 以1为基准能够形成的矩形面积为: 高1宽6 面积6

同理, 以5位基准, 找到第一个元素就小于自己的柱子, 说明自己已经无法向左扩展了,
向右找, 6元素比自己大, 那么自己可以向右扩展, 所以以5为基准所组成的矩形的宽度+1,
再向右找, 就又遇到比当前5小的元素, 说明也不能向右扩展了, 找到了当前元素构成矩形的结果

遍历数组, 以所有元素为基准, 按此规则进行寻找, 获取最大面积值即可

详细思路:
这里涉及单调栈的重要性质, 就是单调栈中的顺序, 是从小到大还是从大到小

因为本题是要找每个柱子左右两边第一个小于该元素的柱子, 所以从栈口到栈底的顺序应该是递减的
所以本题单调栈的顺序正好与接雨水相反

此时可以发现, 其实就是用栈顶元素和栈顶的下一个元素以及要入栈的三个元素组成了要求的最大矩形面积的高度和宽度
主要分析如下三种情况:

	情况1: 当前遍历的元素 > 栈顶元素   heights[i] > height[st.top()]
	情况2: 当前遍历的元素 == 栈顶元素  heights[i] == height[st.top()]
	情况3: 当前遍历的元素 < 栈顶元素   heights[i] < height[st.top()]

细节1: 需要在height数组前后, 都加一个元素0, 为什么这么做呢?

	首先说末尾为什么要加元素0:
		如果数组本身就是升序的, 例如[2,4,6,8], 那么入栈之后都是单调递减, 一直都没有走情况三计算结果的步骤, 那么最后输出的就是0了
		结尾加一个0, 就会让栈立德所有元素, 走到情况3的逻辑
	开头为什么要加元素0?
		如果数组本身是降序的, 例如[8,6,4,2], 在8入栈后, 6开始与8进行比较, 此时得到mid(8), right(6), 但是得不到left
		因为将8弹出之后, 栈里没有元素了, 那么为了避免空栈取值, 直接跳过了计算结果的逻辑
		之后又将6加入栈(此时8已经弹出了), 然后就是4与栈口元素8进行比较, 周而复始, 那么计算的最后结果就是0
*/
func largestRectangleArea(heights []int) int {

	res := 0             //声明最大结果
	st := make([]int, 0) //声明单调栈栈

	heights = append([]int{0}, heights...) //数组头部加入0
	heights = append(heights, 0)           // 数组尾部加入0

	st = append(st, 0) // 初始化栈,先将下标0存入栈中

	for i := 1; i < len(heights); i++ {
		// 结束循环条件为：只要满足栈口元素 > 当前元素，打破了栈的单调递减性, 则构成了矩形面积
		for heights[i] < heights[st[len(st)-1]] {
			mid := st[len(st)-1]  // 取出栈顶元素,作为中间柱子
			st = st[:len(st)-1]   // 弹出栈顶元素
			left := st[len(st)-1] // 左柱子是top的下一位元素，右柱子是当前元素

			tmp := heights[mid] * (i - left - 1) // 高度x宽度
			if tmp > res {
				res = tmp
			}
		}
		st = append(st, i)
	}
	return res
}
